package com.yiwenup.leetcode.offer;

import com.yiwenup.leetcode.TreeNode;

/**
 * https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/
 **/
public class No026 {
    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：40.3 MB, 在所有 Java 提交中击败了25.50%的用户
     */
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        return A != null && B != null && (preOrder(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }

    /**
     * 先序遍历
     */
    public boolean preOrder(TreeNode a, TreeNode b) {
        // B遍历完成
        if (b == null) return true;

        if (a == null || a.val != b.val) return false;

        // 要求B的左子树是A的左子树的部分 且 B的右子树是A的右子树的部分
        return preOrder(a.left, b.left) && preOrder(a.right, b.right);
    }
}
